<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 */
 
/**
 * Class LinkedHashMap
 *
 * Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation 
 * differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list 
 * defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). 
 * Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m 
 * if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)
 * 
 * This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashMap 
 * (and Hashtable), without incurring the increased cost associated with TreeMap. It can be used to produce a copy of a 
 * map that has the same order as the original, regardless of the original map's implementation:
 * 
 * <code>  
 * 	void foo(Map m) {      
 * 		Map copy = new LinkedHashMap(m);
 * 		...
 * 	}
 * </code>
 * 
 * This technique is particularly useful if a module takes a map on input, copies it, and later returns results whose 
 * order is determined by that of the copy. (Clients generally appreciate having things returned in the same order they 
 * were presented.)
 * 
 * A special constructor is provided to create a linked hash map whose order of iteration is the order in which its 
 * entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is 
 * well-suited to building LRU caches. Invoking the put or get method results in an access to the corresponding 
 * entry (assuming it exists after the invocation completes). The putAll method generates one entry access for each 
 * mapping in the specified map, in the order that key-value mappings are provided by the specified map's entry set 
 * iterator. No other methods generate entry accesses. In particular, operations on collection-views do not affect 
 * the order of iteration of the backing map.
 * 
 * The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically 
 * when new mappings are added to the map.
 * 
 * This class provides all of the optional Map operations, and permits null elements. Like HashMap, it provides 
 * constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses 
 * elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the 
 * added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a 
 * LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap 
 * is likely to be more expensive, requiring time proportional to its capacity.
 * 
 * A linked hash map has two parameters that affect its performance: initial capacity and load factor. They are defined 
 * precisely as for HashMap. Note, however, that the penalty for choosing an excessively high value for initial capacity 
 * is less severe for this class than for HashMap, as iteration times for this class are unaffected by capacity.
 * 
 * Note that this implementation is not synchronized. If multiple threads access a linked hash map concurrently, and at 
 * least one of the threads modifies the map structurally, it must be synchronized externally. This is typically accomplished 
 * by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be 
 * "wrapped" using the Collections.synchronizedMapmethod. This is best done at creation time, to prevent accidental 
 * unsynchronized access:
 * 
 * Map m = Collections.synchronizedMap(new LinkedHashMap(...));
 * 
 * A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered 
 * linked hash maps, affects iteration order. In insertion-ordered linked hash maps, merely changing the value associated 
 * with a key that is already contained in the map is not a structural modification. In access-ordered linked hash maps, 
 * merely querying the map with get is a structural modification.)
 * 
 * The iterators returned by the iterator methods of the collections returned by all of this class's collection view 
 * methods are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way 
 * except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, 
 * in the face of concurrent modification, the CollectionIterator fails quickly and cleanly, rather than risking arbitrary, 
 * non-deterministic behavior at an undetermined time in the future.
 * 
 * Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make 
 * any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw 
 * ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that 
 * depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect 
 * bugs.
 * 
 * This class is a member of the PHP Collections Framework. 
 * 
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 */
class LinkedHashMap extends HashMap {
	private $header;
	private $accessOrder;
	
	public function __construct() {
		parent::__construct();
		$this->accessOrder = false;
	}
	
	public function getHeader() {
		return $this->header;
	}
	
	public function init() {
		$this->header = new LinkedHashMap_Entry(-1, null, null, null);
		$this->header->before = $this->header->after = $this->header;
	}
	
	public function transfer( $newCapacity ){
		$newTable = array();
		
		for ($e = $this->header->after; $e !== $this->header; $e = $e->after ) {
			$index = HashMap::indexFor( $e->hash, $newCapacity );
			$e->next = (isset($newTable[$index]) ? $newTable[$index] : null);
			$newTable[$index] = $e;
		}
		
		return $newTable;
	}
	
	
	
	
	public function containsValue( Object $value ) {
		if ($value == null ) {
			for ($e = $this->header->after; $e != $this->header; $e = $e->after)
				if ($e->value == null)
					return true;
		} else {
			for ($e = $this->header->after; $e != $this->header; $e = $e->after)
				if ($value->equals($e->value))
					return true;
		}
		return false;
	}
	
	public function get( Object $key ) {
		$e = $this->getEntry($key);
		if ($e == null)	
			return null;
		$e->recordAccess( $this );
		return $e->value;
	}
	
	public function clear() {
		parent::clear();
		$this->header->before = $this->header->after = $this->header;
	}
	
	public function newKeyIterator() {
		return new LinkedHashMap_KeyIterator( $this );
	}
	public function newValueIterator() {
		return new LinkedHashMap_ValueIterator( $this );
	}
	public function newEntryIterator() {
		return new LinkedHashMap_EntryIterator( $this );
	}


	public function addEntry( $hash, Object $key = null, Object $value = null, $bucketIndex = null ) {
		$this->createEntry( $hash, $key, $value, $bucketIndex );
		
		$eldest = $this->header->after;
		if ($this->removeEldestEntry( $eldest )) {
			$this->removeEldestEntry( $eldest->key );
		} else {
			if ($this->size >= $this->threshold)
				$this->resize( 2 * $this->capacity );
		}
	}
	
	public function createEntry( $hash, Object $key = null, Object $value = null, $bucketIndex = null ) {
		$e = new LinkedHashMap_Entry( $hash, $key, $value, (isset($this->table[$bucketIndex]) ? $this->table[$bucketIndex] : null) );
		$this->table[$bucketIndex] = $e;
		$e->addBefore( $this->header );
		$this->size++;
	}
	
	protected function removeEldestEntry( MapEntry $eldest ) {
		return false;
	}
}
/**
 * 
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 * @internal
 */
class LinkedHashMap_Entry extends HashMap_Entry {
	public $before;
	public $after;
	
	public function __construct( $hash, Object $key = null, Object $value = null, HashMap_Entry $next = null) {
		parent::__construct( $hash, $key, $value, $next );
	}
	
	private function remove() {
		$this->before->after = $this->after;
		$this->after->before = $this->before;
	}
	
	public function addBefore( LinkedHashMap_Entry $existingEntry ) {
		$this->after = $existingEntry;
		$this->before = $existingEntry->before;
		$this->before->after = $this;
		$this->after->before = $this;
	}
	
	public function recordAccess( LinkedHashMap $m ) {
		$lm = $m;
		if ($lm->getAccessOrder() ) {
			$currentMapModCount = $lm->getModCount();
			$lm->setModCount( ++$currentMapModCount );
			$this->remove();
			$this->addBefore( $lm->getHeader() );
		}
	}
	
	public function recordRemoval( LinkedHashMap $m ) {
		$this->remove();
	}
}

/**
 * 
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 * @internal
 */
abstract class LinkedHashMap_Iterator implements CollectionIterator {
	private $map;

	private $nextEntry;
	private $lastReturned = null;
	
	private $expectedModCount;
	
	public function __construct( LinkedHashMap $map ) {
		$this->map = $map;
		$this->nextEntry = $map->getHeader()->after;
		$this->expectedModCount = $map->getModCount();
	}
	
	public function hasNext() {
		return ($this->nextEntry !== $this->map->getHeader());
	}
	
	public function remove() {
		if ($this->lastReturned == null)
			throw new IllegalStateException();
		if ($this->map->getModCount() != $this->expectedModCount )
			throw new ConcurrentModificationException();
	
		$this->map->remove( $this->lastReturned->key );
		$this->lastReturned = null;
		$this->expectedModCount = $this->map->getModCount();
	}
	
	public function nextEntry() {
		if ($this->map->getModCount() != $this->expectedModCount )
			throw new ConcurrentModificationException();
		if ($this->nextEntry === $this->map->getHeader() )
			throw new NoSuchElementException();
			
		$e = $this->lastReturned = $this->nextEntry;
		$this->nextEntry = $e->after;
		return $e;
	}
}

/**
 * 
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 * @internal
 */
class LinkedHashMap_ValueIterator extends LinkedHashMap_Iterator {
	public function next() {
		return $this->nextEntry()->getValue();
	}
	public function getNext() {
		return $this->nextEntry()->getValue();
	}
	
	public function current() {
	
	}
	public function key() {
	
	}
	public function valid() {
	
	}
	public function rewind() {
	
	}
}

/**
 * 
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 * @internal
 */
class LinkedHashMap_KeyIterator extends LinkedHashMap_Iterator {
	public function next() {
		return $this->nextEntry()->getKey();
	}
	public function getNext() {
		return $this->nextEntry()->getKey();
	}
	
	public function current() {
	
	}
	public function key() {
	
	}
	public function valid() {
	
	}
	public function rewind() {
	
	}
}

/**
 * 
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 * @internal
 */
class LinkedHashMap_EntryIterator extends LinkedHashMap_Iterator {
	public function next() {
		return $this->nextEntry();
	}
	public function getNext() {
		return $this->nextEntry();
	}
	
	public function current() {
	
	}
	public function key() {
	
	}
	public function valid() {
	
	}
	public function rewind() {
	
	}
}


?>